package LeetCode.interview;

import LeetCode.interview._021_Merge_Two_Sorted_Lists.ListNode;
import util.LogUtils;

/*
 * 
原题

　　Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. 
　　For example, 
　　Given 1->2->3->3->4->4->5, return 1->2->5. 
　　Given 1->1->1->2->3, return 2->3. 

题目大意

　　给定一个排好序的单链表，删除所有重复的元素。只留下只有一个值的元素。 

解题思路
	与 26 @_026_Remove_Duplicates_from_Sorted 思路相同
 	我们可以将不重复的序列存到数列前面，因为不重复序列的长度一定小于等于总序列，所以不用担心覆盖的问题。
 	具体来说，用两个指针，快指针(i)指向当前数组遍历到的位置，慢指针(end)指向不重复序列下一个存放的位置，
 	这样我们一旦遍历到一个不重复的元素，就把它复制到不重复序列的末尾。判断重复的方法是记录上一个遍历到的数字，看是否一样。
 * @Date 2017-09-13 14：54
 */
public class _083_Remove_Duplicates_from_Sorted_List {
	public class ListNode {
		    int val;
		    ListNode next;
		    ListNode(int x) { val = x; }
	}
    public ListNode deleteDuplicates(ListNode head) {
    	if (head == null)	return null;
    	ListNode pre = head;
    	ListNode p = head.next;
    	ListNode end = head;
    	
    	while (p != null) {
    		if (p.val != pre.val) {
    			end.next = p;
    			end = end.next;
    			pre = end;

    		}
    		p = p.next;
    	}
    	end.next = null;
    	//遍历：看下结果
    	traverse(head);
        return head;
    }

    
    private void traverse(ListNode head) {
//    	for (int i = 0; i < end; i ++) {
//    		LogUtils.print(nums[i]);
//    	}
//    	LogUtils.br();
    	while (head != null) {
    		LogUtils.print(head.val);
    		head = head.next;
    	}
    }
    
	private ListNode newLinkList1() {
		ListNode root = new ListNode(1);
		root.next = new ListNode(1);
		root.next.next = new ListNode(1);
		root.next.next.next = new ListNode(2);
		root.next.next.next.next = new ListNode(2);
		root.next.next.next.next.next = new ListNode(2);
		root.next.next.next.next.next.next = new ListNode(3);
		root.next.next.next.next.next.next.next = new ListNode(3);
		root.next.next.next.next.next.next.next.next = new ListNode(3);
		root.next.next.next.next.next.next.next.next.next = new ListNode(3);
		return root;
	}
	
	private ListNode newLinkList3() {
		ListNode root = new ListNode(1);
		root.next = new ListNode(1);
		root.next.next = new ListNode(2);
		root.next.next.next = new ListNode(3);
		root.next.next.next.next = new ListNode(3);

		return root;
	}
	
	public static void main(String[] args) {
		_083_Remove_Duplicates_from_Sorted_List obj = new _083_Remove_Duplicates_from_Sorted_List();
		obj.deleteDuplicates(obj.newLinkList1());
	}
}
